package lhc.alg.top100;

/**
 * description:
 *
 * https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 * 主要是在于公式的推导
 *
 * author: hongchen.liao
 * date:  2022/7/23
 */
public class _Offer_62 {

    //迭代解法
    class Solution {
        public int lastRemaining(int n, int m) {
            int f = 0;
            for(int i = 2; i != n+1; i++){
                f = (m + f) % i;
            }
            return f;
        }
    }

    //递归解法
    class Solution2 {
        public int lastRemaining(int n, int m) {
            return f(n, m);
        }

        public int f(int n, int m){
            if(n == 1){
                return 0;
            }
            int x = f(n-1, m);
            return (m+x) % n;
        }
    }


}
